SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Binary tree</title>

</head>

Binary tree

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="Binary_search_tree" title="Binary search tree">Binary search tree</a>, <a href="B-tree" title="B-tree">B-tree</a>, or <a href="B%2B_tree" title="B+ tree">B+ tree</a>.</div>

In <a href="Computer_science" title="Computer science">computer science</a>, a binary tree is a <a href="Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">tree data structure</a> in which each node has at most two <a href="Child_node" class="mw-redirect" title="Child node">children</a>, referred to as the left child and the right child. That is, it is a <a href="M-ary_tree" title="M-ary tree">k-ary tree</a> with k = 2. A <a href="Recursive_definition" title="Recursive definition">recursive definition</a> using <a href="Set_theory" title="Set theory">set theory</a> is that a binary tree is a <a href="Triple_(mathematics)" class="mw-redirect" title="Triple (mathematics)">triple</a> (L, S, R), where L and R are binary trees or the <a href="Empty_set" title="Empty set">empty set</a> and S is a <a href="Singleton_(mathematics)" title="Singleton (mathematics)">singleton</a> (a single–element set) containing the root.<a href="#cite_note-GarnierTaylor2009-1">[1]</a><a href="#cite_note-Skiena2009-2">[2]</a>

From a <a href="Graph_theory" title="Graph theory">graph theory</a> perspective, binary trees as defined here are <a href="Arborescence_(graph_theory)" title="Arborescence (graph theory)">arborescences</a>.<a href="#cite_note-Knuth1997-3">[3]</a> A binary tree may thus be also called a bifurcating arborescence,<a href="#cite_note-Knuth1997-3">[3]</a> a term which appears in some early programming books<a href="#cite_note-Flores1971-4">[4]</a> before the modern computer science terminology prevailed. It is also possible to interpret a binary tree as an <a href="Undirected_graph" class="mw-redirect" title="Undirected graph">undirected</a>, rather than <a href="Directed_graph" title="Directed graph">directed graph</a>, in which case a binary tree is an <a href="Ordered_tree" class="mw-redirect" title="Ordered tree">ordered</a>, <a href="Rooted_tree" class="mw-redirect" title="Rooted tree">rooted tree</a>.<a href="#cite_note-5">[5]</a> Some authors use rooted binary tree instead of binary tree to emphasize the fact that the tree is rooted, but as defined above, a binary tree is always rooted.<a href="#cite_note-Mazur2010-6">[6]</a>

In mathematics, what is termed binary tree can vary significantly from author to author. Some use the definition commonly used in computer science,<a href="#cite_note-oem-7">[7]</a> but others define it as every non-leaf having exactly two children and don't necessarily label the children as left and right either.<a href="#cite_note-Foulds1992-8">[8]</a>

In computing, binary trees can be used in two very different ways:

<ul><li>First, as a means of accessing nodes based on some value or label associated with each node.<a href="#cite_note-Makinson2009b-9">[9]</a> Binary trees labelled this way are used to implement <a href="Binary_search_tree" title="Binary search tree">binary search trees</a> and <a href="Binary_heap" title="Binary heap">binary heaps</a>, and are used for efficient <a href="Search_algorithm" title="Search algorithm">searching</a> and <a href="Sorting_algorithm" title="Sorting algorithm">sorting</a>. The designation of non-root nodes as left or right child even when there is only one child present matters in some of these applications, in particular, it is significant in binary search trees.<a href="#cite_note-Gross2007-10">[10]</a> However, the arrangement of particular nodes into the tree is not part of the conceptual information. For example, in a normal binary search tree the placement of nodes depends almost entirely on the order in which they were added, and can be re-arranged (for example by <a href="Self-balancing_binary_search_tree" title="Self-balancing binary search tree">balancing</a>) without changing the meaning.</li>

<li>Second, as a representation of data with a relevant bifurcating structure. In such cases, the particular arrangement of nodes under and/or to the left or right of other nodes is part of the information (that is, changing it would change the meaning). Common examples occur with <a href="Huffman_coding" title="Huffman coding">Huffman coding</a> and <a href="Cladogram" title="Cladogram">cladograms</a>. The everyday division of documents into chapters, sections, paragraphs, and so on is an analogous example with n-ary rather than binary trees.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Definitions">Definitions</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Recursive_definition">Recursive definition</h3></div>

<div class="mw-heading mw-heading4"><h4 id="Recursive_full_tree_definition">Recursive full tree definition</h4></div>

A simple, informal approach to describe a binary tree might be as follows:

<dl><dd>a binary tree has a root node, which has 0 or 2 children nodes (which in turn may have their 0 or 2 children, and so on).</dd></dl>

More formally:

<ul><li>(base case) There exists a <a href="Full_tree" class="mw-redirect" title="Full tree">full tree</a> consisting of a single node;</li>

<li>(recursive step) If T1 and T2 are full binary trees, which do not share any node, and r is a node not belonging to T1 or T2, then the <a href="Ordered_triple" class="mw-redirect" title="Ordered triple">ordered triple</a> (r, T1, T2) is a full binary tree.<a href="#cite_note-Long2018-11">[11]</a></li></ul>

This definition implies two limitations: a full binary tree contains at least one node, and no node can have only one child. This is resolved with the next definition.

<div class="mw-heading mw-heading4"><h4 id="Recursive_extended_tree_definition">Recursive extended tree definition</h4></div>

The extended tree definition starts with the assumption the tree can be empty.

<ul><li>(base case) An empty set of nodes is an extended binary tree.</li>

<li>(recursive step) If T1 and T2 are extended binary trees, which do not share any node, and r is a node not belonging to any of them, then the ordered triple (r, T1, T2) is an extended binary tree.<a href="#cite_note-Rosen2011-12">[12]</a><a href="#cite_note-Long2018-11">[11]</a></li></ul>

To be complete from the graph point of view, both definitions of a tree should be extended by a definition of the corresponding branches sets. Informally, the branches set can be described as a set of all ordered pairs of nodes (r, s) where r is a root node of any subtree appearing in the definition, and s is a root node of any of its T1 and T2 subtrees (in case the respective subtree is not empty).

Another way of imagining this construction (and understanding the terminology) is to consider instead of the empty set a different type of node—for instance square nodes if the regular ones are circles.<a href="#cite_note-HuShing2002-13">[13]</a>

<div class="mw-heading mw-heading3"><h3 id="Using_graph_theory_concepts">Using graph theory concepts</h3></div>

A binary tree is a <a href="Rooted_tree" class="mw-redirect" title="Rooted tree">rooted tree</a> that is also an <a href="Ordered_tree" class="mw-redirect" title="Ordered tree">ordered tree</a> (a.k.a. plane tree) in which every node has at most two children. A rooted tree naturally imparts a notion of levels (distance from the root); thus, for every node, a notion of children may be defined as the nodes connected to it a level below. Ordering of these children (e.g., by drawing them on a plane) makes it possible to distinguish a left child from a right child.<a href="#cite_note-HsuLin2008-14">[14]</a> But this still does not distinguish between a node with left but not a right child from a node with right but no left child.

The necessary distinction can be made by first partitioning the edges; i.e., defining the binary tree as triplet (V, E1, E2), where (V, E1 ∪ E2) is a rooted tree (equivalently arborescence) and E1 ∩ E2 is empty, and also requiring that for all j ∈ { 1, 2 }, every node has at most one Ej child.<a href="#cite_note-FlumGrohe2006-15">[15]</a> A more informal way of making the distinction is to say, quoting the <a href="Encyclopedia_of_Mathematics" title="Encyclopedia of Mathematics">Encyclopedia of Mathematics</a>, that "every node has a left child, a right child, neither, or both" and to specify that these "are all different" binary trees.<a href="#cite_note-oem-7">[7]</a>

<div class="mw-heading mw-heading2"><h2 id="Types_of_binary_trees">Types of binary trees</h2></div>

Tree terminology is not well-standardized and therefore may vary among examples in the available literature.

/* start https://en.wikipedia.org/ */

.mw-parser-output .vanchor>:target~.vanchor-text{background-color:#b1d2ff}@media screen{html.skin-theme-clientpref-night .mw-parser-output .vanchor>:target~.vanchor-text{background-color:#0f4dc9}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .vanchor>:target~.vanchor-text{background-color:#0f4dc9}}

/* end https://en.wikipedia.org/ */

</style>rooted binary <a href="Tree_data_structure" class="mw-redirect" title="Tree data structure">tree</a> has a <a href="Root_node" class="mw-redirect" title="Root node">root node</a> and every node has at most two children.</li></ul>

<ul><li>A full binary tree (sometimes referred to as a proper,<a href="#cite_note-16">[16]</a> plane, or strict binary tree)<a href="#cite_note-17">[17]</a><a href="#cite_note-18">[18]</a> is a tree in which every node has either 0 or 2 children. Another way of defining a full binary tree is a <a href="Recursive_definition" title="Recursive definition">recursive definition</a>. A full binary tree is either:<a href="#cite_note-Rosen2011-12">[12]</a>

<ul><li>A single vertex (a single node as the root node).</li>

<li>A tree whose root node has two subtrees, both of which are full binary trees.</li></ul></li>

<li>A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level (the level of a node defined as the number of edges or links from the root node to a node).<a href="#cite_note-19">[19]</a> A perfect binary tree is a full binary tree.</li>

<li>A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes at the last level h.<a href="#cite_note-complete_binary_tree-20">[20]</a> A perfect tree is therefore always complete but a complete tree is not always perfect. Some authors use the term complete to refer instead to a perfect binary tree as defined above, in which case they call this type of tree (with a possibly not filled last level) an almost complete binary tree or nearly complete binary tree.<a href="#cite_note-almost_complete_binary_tree-21">[21]</a><a href="#cite_note-nearly_complete_binary_tree-22">[22]</a> A complete binary tree can be efficiently represented using an array.<a href="#cite_note-complete_binary_tree-20">[20]</a></li></ul>

<ul><li>The infinite complete binary tree is a tree with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\aleph _{0}}}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\aleph _{0}}}</annotation>

</semantics>

</math><img src="./98d41341ae020c937dee3df105f059eb93ed96c8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.475ex; height:2.509ex;" alt="{\displaystyle {\aleph _{0}}}" loading="lazy"> levels, where for each level d the number of existing nodes at level d is equal to 2d. The cardinal number of the set of all levels is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\aleph _{0}}}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\aleph _{0}}}</annotation>

</semantics>

</math><img src="./98d41341ae020c937dee3df105f059eb93ed96c8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.475ex; height:2.509ex;" alt="{\displaystyle {\aleph _{0}}}" loading="lazy"> (countably infinite). The cardinal number of the set of all paths (the "leaves", so to speak) is uncountable, having the <a href="Cardinality_of_the_continuum" title="Cardinality of the continuum">cardinality of the continuum</a>.</li>

<li>A balanced binary tree is a binary tree structure in which the left and right subtrees of every node differ in height (the number of edges from the top-most node to the farthest node in a subtree) by no more than 1 (or the skew is no greater than 1).<a href="#cite_note-23">[23]</a> One may also consider binary trees where no leaf is much farther away from the root than any other leaf. (Different balancing schemes allow different definitions of "much farther".<a href="#cite_note-24">[24]</a>)</li>

<li>A degenerate (or pathological) tree is where each parent node has only one associated child node.<a href="#cite_note-25">[25]</a> This means that the tree will behave like a <a href="Linked_list" title="Linked list">linked list</a> data structure. In this case, an advantage of using a binary tree is significantly reduced because it is essentially a linked list which <a href="Time_complexity" title="Time complexity">time complexity</a> is O(n) (n as the number of nodes and 'O()' being the <a href="Big_O_notation" title="Big O notation">Big O notation</a>) and it has more data space than the linked list due to two pointers per node, while the complexity of O(log2 n) for data search in a balanced binary tree is normally expected.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Properties_of_binary_trees">Properties of binary trees</h2></div>

<ul><li>The number of nodes n in a full binary tree is at least <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2h+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2h+1}</annotation>

</semantics>

</math><img src="./29cf886c7e158d979280e2f2543017776723b063.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.504ex; height:2.343ex;" alt="{\displaystyle 2h+1}" loading="lazy"> and at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{h+1}-1}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{h+1}-1}</annotation>

</semantics>

</math><img src="./942650818fce75c77b1e2b0941ca54e01434bdbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.445ex; height:2.843ex;" alt="{\displaystyle 2^{h+1}-1}" loading="lazy"> (i.e., the number of nodes in a perfect binary tree), where h is the <a href="Glossary_of_graph_theory_terms" class="mw-redirect" title="Glossary of graph theory terms">height</a> of the tree. A tree consisting of only a root node has a height of 0. The least number of nodes is obtained by adding only two children nodes per adding height so <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2h+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2h+1}</annotation>

</semantics>

</math><img src="./29cf886c7e158d979280e2f2543017776723b063.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.504ex; height:2.343ex;" alt="{\displaystyle 2h+1}" loading="lazy"> (1 for counting the root node). The maximum number of nodes is obtained by fully filling nodes at each level, i.e., it is a perfect tree. For a perfect tree, the number of nodes is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1+2+4+\ldots +2^{h}=2^{h+1}-1}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1+2+4+\ldots +2^{h}=2^{h+1}-1}</annotation>

</semantics>

</math><img src="./5bbe6ec1ae9871eb6794866199acf1176803ee99.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:31.457ex; height:2.843ex;" alt="{\displaystyle 1+2+4+\ldots +2^{h}=2^{h+1}-1}" loading="lazy">, where the last equality is from the <a href="Geometric_series" title="Geometric series">geometric series</a> sum.</li>

<li>The number of leaf nodes l in a perfect binary tree is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l=(n+1)/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l=(n+1)/2}</annotation>

</semantics>

</math><img src="./52f9a12bb66ec9a46656d9f008dfce4219375897.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.324ex; height:2.843ex;" alt="{\displaystyle l=(n+1)/2}" loading="lazy"> (where n is the number of nodes in the tree) because <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n={{2}^{h+1}}-1}">

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n={{2}^{h+1}}-1}</annotation>

</semantics>

</math><img src="./5f1cce45a9eb7e21d90a013a98d72f209c03c424.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:12.938ex; height:2.843ex;" alt="{\displaystyle n={{2}^{h+1}}-1}" loading="lazy"> (by using the above property) and the number of leaves is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{h}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{h}}</annotation>

</semantics>

</math><img src="./d07258f211ef9a26565e6db98c01d57229171c0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.342ex; height:2.676ex;" alt="{\displaystyle 2^{h}}" loading="lazy"> so <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=2\cdot {{2}^{h}}-1=2l-1\to l=\left(n+1\right)/2}">

<msup>

</mrow>

</mrow>

</msup>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=2\cdot {{2}^{h}}-1=2l-1\to l=\left(n+1\right)/2}</annotation>

</semantics>

</math><img src="./509db81fe22a735f557489043cf4bea83fb3fac0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:39.961ex; height:3.176ex;" alt="{\displaystyle n=2\cdot {{2}^{h}}-1=2l-1\to l=\left(n+1\right)/2}" loading="lazy">. It also means that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=2l-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=2l-1}</annotation>

</semantics>

</math><img src="./6c6e89428a9bb787bd2d029f3bb0740c75c45da3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.352ex; height:2.343ex;" alt="{\displaystyle n=2l-1}" loading="lazy">. In terms of the tree height h, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l=(2^{h+1}-1+1)/2=2^{h}}">

<msup>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l=(2^{h+1}-1+1)/2=2^{h}}</annotation>

</semantics>

</math><img src="./6c2e2fbd1232cf71700d8b02bf8070411096a74c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.814ex; height:3.176ex;" alt="{\displaystyle l=(2^{h+1}-1+1)/2=2^{h}}" loading="lazy">.</li>

<li>For any non-empty binary tree with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l}</annotation>

</semantics>

</math><img src="./829091f745070b9eb97a80244129025440a1cfac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.693ex; height:2.176ex;" alt="{\displaystyle l}" loading="lazy"> leaf nodes and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i_{2}}</annotation>

</semantics>

</math><img src="./14feff7997a635a64f7dfacfbd0374a24ab279bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.857ex; height:2.509ex;" alt="{\displaystyle i_{2}}" loading="lazy"> nodes of degree 2 (internal nodes with two child nodes), <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l=i_{2}+1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l=i_{2}+1}</annotation>

</semantics>

</math><img src="./186942c8ccec8daf28e5d42bb40adee090b1b929.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.651ex; height:2.509ex;" alt="{\displaystyle l=i_{2}+1}" loading="lazy">.<a href="#cite_note-26">[26]</a> The proof is the following. For a perfect binary tree, the total number of nodes is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=2^{h+1}-1}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=2^{h+1}-1}</annotation>

</semantics>

</math><img src="./3558d5feb47029b11259917bbb81b6c14a5da484.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:12.938ex; height:2.843ex;" alt="{\displaystyle n=2^{h+1}-1}" loading="lazy"> (A perfect binary tree is a full binary tree.) and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l=2^{h}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l=2^{h}}</annotation>

</semantics>

</math><img src="./0c75a8ef2ff68abf9711a5952953e0ee7ab98284.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.133ex; height:2.676ex;" alt="{\displaystyle l=2^{h}}" loading="lazy">, so <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i=n-l=(2^{h+1}-1)-2^{h}=2^{h}-1=l-1\to l=i+1}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i=n-l=(2^{h+1}-1)-2^{h}=2^{h}-1=l-1\to l=i+1}</annotation>

</semantics>

</math><img src="./1f5dd47ad4c1c7f3fe816e9010278cbe841a0c05.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:56.812ex; height:3.176ex;" alt="{\displaystyle i=n-l=(2^{h+1}-1)-2^{h}=2^{h}-1=l-1\to l=i+1}" loading="lazy">. To make a full binary tree from a perfect binary tree, a pair of two sibling nodes are removed one by one. This results in "two leaf nodes removed" and "one internal node removed" and "the removed internal node becoming a leaf node", so one leaf node and one internal node is removed per removing two sibling nodes. As a result, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l=i+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l=i+1}</annotation>

</semantics>

</math><img src="./9e57994678f0e8eed4daa9c2d4c2825e406d380e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.597ex; height:2.343ex;" alt="{\displaystyle l=i+1}" loading="lazy"> also holds for a full binary tree. To make a binary tree with a leaf node without its sibling, a single leaf node is removed from a full binary tree, then "one leaf node removed" and "one internal nodes with two children removed" so <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l=i+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l=i+1}</annotation>

</semantics>

<li>With given n nodes, the minimum possible tree height is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{\min }=\log _{2}(n+1)-1}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{\min }=\log _{2}(n+1)-1}</annotation>

</semantics>

</math><img src="./75480646a39fe5df8a9dabb74befeee3376b5541.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.646ex; height:2.843ex;" alt="{\displaystyle h_{\min }=\log _{2}(n+1)-1}" loading="lazy"> with which the tree is a balanced full tree or perfect tree. With a given height h, the number of nodes can't exceed the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{h+1}-1}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{h+1}-1}</annotation>

</semantics>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\leq 2^{h+1}-1\to h\geq \log _{2}(n+1)-1}</annotation>

</semantics>

</math><img src="./052f216a5a614a79fa1f078f162c3bb654b2261b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:36.225ex; height:3.176ex;" alt="{\displaystyle n\leq 2^{h+1}-1\to h\geq \log _{2}(n+1)-1}" loading="lazy">.</li>

<li>A binary Tree with l leaves has at least the height <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{m}=\log _{2}(l)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h_{m}=\log _{2}(l)}</annotation>

</semantics>

</math><img src="./b3a337a47a83f4253de9c49198c6a04bd9dc9ca4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.641ex; height:2.843ex;" alt="{\displaystyle h_{m}=\log _{2}(l)}" loading="lazy">. With a given height h, the number of leaves at that height can't exceed <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{h}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{h}}</annotation>

</semantics>

</math><img src="./d07258f211ef9a26565e6db98c01d57229171c0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.342ex; height:2.676ex;" alt="{\displaystyle 2^{h}}" loading="lazy"> as the number of leaves at the height in a perfect tree. Thus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle l\leq 2^{h}\to h\geq \log _{2}(l)}">

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle l\leq 2^{h}\to h\geq \log _{2}(l)}</annotation>

</semantics>

</math><img src="./7a0fe474a16adfbc1affeb5868c80af091eca74c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.713ex; height:3.176ex;" alt="{\displaystyle l\leq 2^{h}\to h\geq \log _{2}(l)}" loading="lazy">.</li>

<li>In a non-empty binary tree, if n is the total number of nodes and e is the total number of edges, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e=n-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e=n-1}</annotation>

</semantics>

</math><img src="./0e5e836de7729863adeeb853402388b5b48c4df7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.58ex; height:2.343ex;" alt="{\displaystyle e=n-1}" loading="lazy">. This is obvious because each node requires one edge except for the root node.</li>

<li>The number of null links (i.e., absent children of the nodes) in a binary tree of n nodes is (n + 1).</li>

<li>The number of internal nodes in a complete binary tree of n nodes is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lfloor n/2\rfloor }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lfloor n/2\rfloor }</annotation>

</semantics>

</math><img src="./c86b5dc915aaa6792f2a7d3ed1c165c555256c7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.784ex; height:2.843ex;" alt="{\displaystyle \lfloor n/2\rfloor }" loading="lazy">.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Combinatorics">Combinatorics</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

In <a href="Combinatorics" title="Combinatorics">combinatorics</a>, one considers the problem of counting the number of full binary trees of a given size. Here the trees have no values attached to their nodes (this would just multiply the number of possible trees by an easily determined factor), and trees are distinguished only by their structure; however, the left and right child of any node are distinguished (if they are different trees, then interchanging them will produce a tree distinct from the original one). The size of the tree is taken to be the number n of internal nodes (those with two children); the other nodes are leaf nodes and there are n + 1 of them. The number of such binary trees of size n is equal to the number of ways of fully parenthesizing a string of n + 1 symbols (representing leaves) separated by n binary operators (representing internal nodes), to determine the argument subexpressions of each operator. For instance for n = 3 one has to parenthesize a string like ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X*X*X*X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X*X*X*X}</annotation>

</semantics>

</math><img src="./566156aef575e6ff5ca67b2611ab3fcd127a0c0e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:14.504ex; height:2.176ex;" alt="{\displaystyle X*X*X*X}" loading="lazy">⁠, which is possible in five ways:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ((X*X)*X)*X,\qquad (X*(X*X))*X,\qquad (X*X)*(X*X),\qquad X*((X*X)*X),\qquad X*(X*(X*X)).}</annotation>

</semantics>

</math></dd></dl>

The correspondence to binary trees should be obvious, and the addition of redundant parentheses (around an already parenthesized expression or around the full expression) is disallowed (or at least not counted as producing a new possibility).

There is a unique binary tree of size 0 (consisting of a single leaf), and any other binary tree is characterized by the pair of its left and right children; if these have sizes i and j respectively, the full tree has size i + j + 1. Therefore, the number <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{n}}</annotation>

</semantics>

</math><img src="./0301812adb392070d834ca2df4ed97f1cf132f33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.88ex; height:2.509ex;" alt="{\displaystyle C_{n}}" loading="lazy"> of binary trees of size n has the following recursive description <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{0}=1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{0}=1}</annotation>

</semantics>

</math><img src="./8f16d74f9b1af01a229f5b576167e4f1d7969c83.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.977ex; height:2.509ex;" alt="{\displaystyle C_{0}=1}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \textstyle C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}}</annotation>

</semantics>

</math><img src="./08ba36c0b93072eb89e77290c4f4188741f8f60b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:21.427ex; height:3.509ex;" alt="{\displaystyle \textstyle C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}}" loading="lazy"> for any positive integer n. It follows that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{n}}</annotation>

</semantics>

The above parenthesized strings should not be confused with the set of words of length 2n in the <a href="Dyck_language" title="Dyck language">Dyck language</a>, which consist only of parentheses in such a way that they are properly balanced. The number of such strings satisfies the same recursive description (each Dyck word of length 2n is determined by the Dyck subword enclosed by the initial '(' and its matching ')' together with the Dyck subword remaining after that closing parenthesis, whose lengths 2i and 2j satisfy i + j + 1 = n); this number is therefore also the Catalan number <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{n}}</annotation>

</semantics>

These Dyck words do not correspond to binary trees in the same way. Instead, they are related by the following recursively defined bijection: the Dyck word equal to the empty string corresponds to the binary tree of size 0 with only one leaf. Any other Dyck word can be written as (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{1}}</annotation>

</semantics>

</math><img src="./2f6728d2b30f42f88b52281be5ae0584fdc9df64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.718ex; height:2.009ex;" alt="{\displaystyle w_{1}}" loading="lazy">)<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{2}}</annotation>

</semantics>

</math><img src="./8998e0957bb573a19e7d9d934ced62ee68ab8fb8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.718ex; height:2.009ex;" alt="{\displaystyle w_{2}}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{1}}</annotation>

</semantics>

</math><img src="./2f6728d2b30f42f88b52281be5ae0584fdc9df64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.718ex; height:2.009ex;" alt="{\displaystyle w_{1}}" loading="lazy">,<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{2}}</annotation>

</semantics>

</math><img src="./8998e0957bb573a19e7d9d934ced62ee68ab8fb8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.718ex; height:2.009ex;" alt="{\displaystyle w_{2}}" loading="lazy"> are themselves (possibly empty) Dyck words and where the two written parentheses are matched. The bijection is then defined by letting the words <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{1}}</annotation>

</semantics>

</math><img src="./2f6728d2b30f42f88b52281be5ae0584fdc9df64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.718ex; height:2.009ex;" alt="{\displaystyle w_{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{2}}</annotation>

</semantics>

A bijective correspondence can also be defined as follows: enclose the Dyck word in an extra pair of parentheses, so that the result can be interpreted as a <a href="Lisp_(programming_language)" title="Lisp (programming language)">Lisp</a> list expression (with the empty list () as only occurring atom); then the <a href="Lisp_(programming_language)#S-expressions_represent_lists" title="Lisp (programming language)">dotted-pair</a> expression for that proper list is a fully parenthesized expression (with NIL as symbol and '.' as operator) describing the corresponding binary tree (which is, in fact, the internal representation of the proper list).

The ability to represent binary trees as strings of symbols and parentheses implies that binary trees can represent the elements of a <a href="Free_magma" class="mw-redirect" title="Free magma">free magma</a> on a singleton set.

<div class="mw-heading mw-heading2"><h2 id="Methods_for_storing_binary_trees">Methods for storing binary trees</h2></div>

Binary trees can be constructed from <a href="Programming_language" title="Programming language">programming language</a> primitives in several ways.

<div class="mw-heading mw-heading3"><h3 id="Nodes_and_references">Nodes and references</h3></div>

In a language with <a href="Record_(computer_science)" title="Record (computer science)">records</a> and <a href="Reference_(computer_science)" title="Reference (computer science)">references</a>, binary trees are typically constructed by having a tree node structure which contains some data and references to its left child and its right child. Sometimes it also contains a reference to its unique parent. If a node has fewer than two children, some of the child pointers may be set to a special null value, or to a special <a href="Sentinel_node" title="Sentinel node">sentinel node</a>.

This method of storing binary trees wastes a fair bit of memory, as the pointers will be null (or point to the sentinel) more than half the time; a more conservative representation alternative is <a href="Threaded_binary_tree" title="Threaded binary tree">threaded binary tree</a>.<a href="#cite_note-Samanta2004-27">[27]</a>

In languages with <a href="Tagged_union" title="Tagged union">tagged unions</a> such as <a href="ML_(programming_language)" title="ML (programming language)">ML</a>, a tree node is often a tagged union of two types of nodes, one of which is a 3-tuple of data, left child, and right child, and the other of which is a "leaf" node, which contains no data and functions much like the null value in a language with pointers. For example, the following line of code in <a href="OCaml" title="OCaml">OCaml</a> (an ML dialect) defines a binary tree that stores a character in each node.<a href="#cite_note-Scott2009-28">[28]</a>

<div class="mw-highlight mw-highlight-lang-ocaml mw-content-ltr" dir="ltr"><pre>type chr_tree = Empty | Node of char * chr_tree * chr_tree

</pre></div>

<div class="mw-heading mw-heading3"><h3 id="Arrays">Arrays</h3></div>

Binary trees can also be stored in breadth-first order as an <a href="Implicit_data_structure" title="Implicit data structure">implicit data structure</a> in <a href="Array_data_structure" class="mw-redirect" title="Array data structure">arrays</a>, and if the tree is a complete binary tree, this method wastes no space. In this compact arrangement, if a node has an index i, its children are found at indices <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2i+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2i+1}</annotation>

</semantics>

</math><img src="./f077f73c2ecdf3c6e29a120f948a7255c0a65da1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.968ex; height:2.343ex;" alt="{\displaystyle 2i+1}" loading="lazy"> (for the left child) and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2i+2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2i+2}</annotation>

</semantics>

</math><img src="./a756deaef520ee23fe2b1232c90957f55ec9d92b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.968ex; height:2.343ex;" alt="{\displaystyle 2i+2}" loading="lazy"> (for the right), while its parent (if any) is found at index <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\lfloor {\frac {i-1}{2}}\right\rfloor }">

<mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\lfloor {\frac {i-1}{2}}\right\rfloor }</annotation>

</semantics>

</math><img src="./35dc2d601bbd9aff8f1ed1c4b2323122f2403317.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:8.352ex; height:6.176ex;" alt="{\displaystyle \left\lfloor {\frac {i-1}{2}}\right\rfloor }" loading="lazy"> (assuming the root has index zero). Alternatively, with a 1-indexed array, the implementation is simplified with children found at <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2i}</annotation>

</semantics>

</math><img src="./717fa22d62566808b398d03504bc04a9599da936.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.965ex; height:2.176ex;" alt="{\displaystyle 2i}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2i+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2i+1}</annotation>

</semantics>

</math><img src="./f077f73c2ecdf3c6e29a120f948a7255c0a65da1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.968ex; height:2.343ex;" alt="{\displaystyle 2i+1}" loading="lazy">, and parent found at <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lfloor i/2\rfloor }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lfloor i/2\rfloor }</annotation>

</semantics>

</math><img src="./3dfc70beb8478160c4f60e393a9eaa1cfdb090c2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.192ex; height:2.843ex;" alt="{\displaystyle \lfloor i/2\rfloor }" loading="lazy">.<a href="#cite_note-29">[29]</a>

This method benefits from more compact storage and better <a href="Locality_of_reference" title="Locality of reference">locality of reference</a>, particularly during a preorder traversal. It is often used for <a href="Binary_heap" title="Binary heap">binary heaps</a>.<a href="#cite_note-30">[30]</a>

<div class="mw-heading mw-heading2"><h2 id="Encodings">Encodings</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Succinct_encodings">Succinct encodings</h3></div>

A <a href="Succinct_data_structure" title="Succinct data structure">succinct data structure</a> is one which occupies close to minimum possible space, as established by <a href="Information_theory" title="Information theory">information theoretical</a> lower bounds. The number of different binary trees on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> nodes is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {C} _{n}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {C} _{n}}</annotation>

</semantics>

</math><img src="./c9cd15d2dd0b4299b0ae5953cff1274b283f239e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.897ex; height:2.509ex;" alt="{\displaystyle \mathrm {C} _{n}}" loading="lazy">, the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">th <a href="Catalan_number" title="Catalan number">Catalan number</a> (assuming we view trees with identical structure as identical). For large <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, this is about <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 4^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 4^{n}}</annotation>

</semantics>

</math><img src="./bcdd6057d8f9857a7d45670ced53881c2e312f34.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 4^{n}}" loading="lazy">; thus we need at least about <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{2}4^{n}=2n}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log _{2}4^{n}=2n}</annotation>

</semantics>

</math><img src="./967f4edcd69d8a66cc4f77b9117c10596058c503.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.45ex; height:2.843ex;" alt="{\displaystyle \log _{2}4^{n}=2n}" loading="lazy"> bits to encode it. A succinct binary tree therefore would occupy 2n+o(n) bits (with 'o()' being the <a href="Little-o_notation" class="mw-redirect" title="Little-o notation">Little-o notation</a>).

One simple representation which meets this bound is to visit the nodes of the tree in preorder, outputting "1" for an internal node and "0" for a leaf.<a href="#cite_note-31">[31]</a> If the tree contains data, we can simply simultaneously store it in a consecutive array in preorder. This function accomplishes this:

<pre>function EncodeSuccinct(node n, bitstring structure, array data) {

if n = nil then

append 0 to structure;

else

append 1 to structure;

append n.data to data;

EncodeSuccinct(n.left, structure, data);

EncodeSuccinct(n.right, structure, data);

}

</pre>

The string structure has only <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2n+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2n+1}</annotation>

</semantics>

</math><img src="./8ca410f731fe4c7c444330343afb1d1850eadaea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.56ex; height:2.343ex;" alt="{\displaystyle 2n+1}" loading="lazy"> bits in the end, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

<pre>function DecodeSuccinct(bitstring structure, array data) {

remove first bit of structure and put it in b

if b = 1 then

create a new node n

remove first element of data and put it in n.data

n.left = DecodeSuccinct(structure, data)

n.right = DecodeSuccinct(structure, data)

return n

else

return nil

}

</pre>

More sophisticated succinct representations allow not only compact storage of trees but even useful operations on those trees directly while they're still in their succinct form.

<div class="mw-heading mw-heading3"><h3 id="Encoding_ordered_trees_as_binary_trees">Encoding ordered trees as binary trees</h3></div>

There is a natural one-to-one correspondence between ordered trees and binary trees. It allows any ordered tree to be uniquely represented as a binary tree, and vice versa:

Let T be a node of an ordered tree, and let B denote T's image in the corresponding binary tree. Then B's left child represents T's first child, while the B's right child represents T's next sibling.

For example, the ordered tree on the left and the binary tree on the right correspond:

In the pictured binary tree, the black, left, edges represent first child, while the blue, right, edges represent next sibling.

This representation is called a <a href="Left-child_right-sibling_binary_tree" title="Left-child right-sibling binary tree">left-child right-sibling binary tree</a>.

<div class="mw-heading mw-heading2"><h2 id="Common_operations">Common operations</h2></div>

There are a variety of different operations that can be performed on binary trees. Some are <a href="Mutator_method" title="Mutator method">mutator</a> operations, while others simply return useful information about the tree.

<div class="mw-heading mw-heading3"><h3 id="Insertion">Insertion</h3></div>

Nodes can be inserted into binary trees in between two other nodes or added after a <a href="Leaf_node" class="mw-redirect" title="Leaf node">leaf node</a>. In binary trees, a node that is inserted is specified as to whose child it will be.

<div class="mw-heading mw-heading4"><h4 id="Leaf_nodes">Leaf nodes</h4></div>

To add a new node after leaf node A, A assigns the new node as one of its children and the new node assigns node A as its parent.

<div class="mw-heading mw-heading4"><h4 id="Internal_nodes">Internal nodes</h4></div>

Insertion on <a href="Internal_node" class="mw-redirect" title="Internal node">internal nodes</a> is slightly more complex than on leaf nodes. Say that the internal node is node A and that node B is the child of A. (If the insertion is to insert a right child, then B is the right child of A, and similarly with a left child insertion.) A assigns its child to the new node and the new node assigns its parent to A. Then the new node assigns its child to B and B assigns its parent as the new node.

<div class="mw-heading mw-heading3"><h3 id="Deletion">Deletion</h3></div>

Deletion is the process whereby a node is removed from the tree. Only certain nodes in a binary tree can be removed unambiguously.<a href="#cite_note-rice-32">[32]</a>

<div class="mw-heading mw-heading4"><h4 id="Node_with_zero_or_one_children">Node with zero or one children</h4></div>

Suppose that the node to delete is node A. If A has no children, deletion is accomplished by setting the child of A's parent to <a href="Null_pointer" title="Null pointer">null</a>. If A has one child, set the parent of A's child to A's parent and set the child of A's parent to A's child.

<div class="mw-heading mw-heading4"><h4 id="Node_with_two_children">Node with two children</h4></div>

In a binary tree, a node with two children cannot be deleted unambiguously.<a href="#cite_note-rice-32">[32]</a> However, in certain binary trees (including <a href="Binary_search_tree" title="Binary search tree">binary search trees</a>) these nodes can be deleted, though with a rearrangement of the tree structure.

<div class="mw-heading mw-heading3"><h3 id="Traversal">Traversal</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Tree_traversal" title="Tree traversal">Tree traversal</a></div>

Pre-order, in-order, and post-order traversal visit each node in a tree by recursively visiting each node in the left and right subtrees of the root. Below are the brief descriptions of above mentioned traversals.

<div class="mw-heading mw-heading4"><h4 id="Pre-order">Pre-order</h4></div>

In pre-order, we always visit the current node; next, we recursively traverse the current node's left subtree, and then we recursively traverse the current node's right subtree. The pre-order traversal is a <a href="Topological_sorting" title="Topological sorting">topologically sorted</a> one, because a parent node is processed before any of its child nodes is done.

<div class="mw-heading mw-heading4"><h4 id="In-order">In-order</h4></div>

In in-order, we always recursively traverse the current node's left subtree; next, we visit the current node, and lastly, we recursively traverse the current node's right subtree.

<div class="mw-heading mw-heading4"><h4 id="Post-order">Post-order</h4></div>

In post-order, we always recursively traverse the current node's left subtree; next, we recursively traverse the current node's right subtree and then visit the current node. Post-order traversal can be useful to get postfix expression of a <a href="Binary_expression_tree" title="Binary expression tree">binary expression tree</a>.<a href="#cite_note-33">[33]</a>

<div class="mw-heading mw-heading4"><h4 id="Depth-first_order">Depth-first order</h4></div>

In depth-first order, we always attempt to visit the node farthest from the root node that we can, but with the caveat that it must be a child of a node we have already visited. Unlike a depth-first search on graphs, there is no need to remember all the nodes we have visited, because a tree cannot contain cycles. Pre-order is a special case of this. See <a href="Depth-first_search" title="Depth-first search">depth-first search</a> for more information.

<div class="mw-heading mw-heading4"><h4 id="Breadth-first_order">Breadth-first order</h4></div>

Contrasting with depth-first order is breadth-first order, which always attempts to visit the node closest to the root that it has not already visited. See <a href="Breadth-first_search" title="Breadth-first search">breadth-first search</a> for more information. Also called a level-order traversal.

In a complete binary tree, a node's breadth-index (i − (2d − 1)) can be used as traversal instructions from the root. Reading bitwise from left to right, starting at bit d − 1, where d is the node's distance from the root (d = ⌊log2(i+1)⌋) and the node in question is not the root itself (d > 0). When the breadth-index is masked at bit d − 1, the bit values <style data-mw-deduplicate="TemplateStyles:r886049734">

/* start https://en.wikipedia.org/ */

.mw-parser-output .monospaced{font-family:monospace,monospace}

/* end https://en.wikipedia.org/ */

</style>0 and 1 mean to step either left or right, respectively. The process continues by successively checking the next bit to the right until there are no more. The rightmost bit indicates the final traversal from the desired node's parent to the node itself. There is a time-space trade-off between iterating a complete binary tree this way versus each node having pointer(s) to its sibling(s).

/* start https://en.wikipedia.org/ */

.mw-parser-output .div-col{margin-top:0.3em;column-width:30em}.mw-parser-output .div-col-small{font-size:90%}.mw-parser-output .div-col-rules{column-rule:1px solid #aaa}.mw-parser-output .div-col dl,.mw-parser-output .div-col ol,.mw-parser-output .div-col ul{margin-top:0}.mw-parser-output .div-col li,.mw-parser-output .div-col dd{page-break-inside:avoid;break-inside:avoid-column}

/* end https://en.wikipedia.org/ */

</style><div class="div-col" style="column-width: 30em;">

<li><a href="Ahnentafel" title="Ahnentafel">Ahnentafel</a></li>

<li><a href="Binary_space_partitioning" title="Binary space partitioning">Binary space partitioning</a></li>

<li><a href="Huffman_tree" class="mw-redirect" title="Huffman tree">Huffman tree</a></li>

<li><a href="Kraft's_inequality" class="mw-redirect" title="Kraft's inequality">Kraft's inequality</a></li>

<li><a href="Optimal_binary_search_tree" title="Optimal binary search tree">Optimal binary search tree</a></li>

<li><a href="Random_binary_tree" title="Random binary tree">Random binary tree</a></li>

<li><a href="Recursion_(computer_science)" title="Recursion (computer science)">Recursion (computer science)</a></li>

<li><a href="Red%E2%80%93black_tree" title="Red–black tree">Red–black tree</a></li>

<li><a href="Rope_(computer_science)" class="mw-redirect" title="Rope (computer science)">Rope (computer science)</a></li>

<li><a href="Self-balancing_binary_search_tree" title="Self-balancing binary search tree">Self-balancing binary search tree</a></li>

<li><a href="Splay_tree" title="Splay tree">Splay tree</a></li>

<li><a href="Strahler_number" title="Strahler number">Strahler number</a></li>

<li><a href="Tree_of_primitive_Pythagorean_triples#Alternative_methods_of_generating_the_tree" title="Tree of primitive Pythagorean triples">Tree of primitive Pythagorean triples#Alternative methods of generating the tree</a></li>

<li><a href="Unrooted_binary_tree" title="Unrooted binary tree">Unrooted binary tree</a></li></ul></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Citations">Citations</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 33em;">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFRowan_GarnierJohn_Taylor2009" class="citation book cs1">Rowan Garnier; John Taylor (2009). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=WnkZSSc4IkoC&pg=PA620">Discrete Mathematics:Proofs, Structures and Applications, Third Edition</a>. CRC Press. p. 620. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4398-1280-8</bdi>.</cite>

</li>

<li id="cite_note-Skiena2009-2"><a href="#cite_ref-Skiena2009_2-0">^</a> <cite id="CITEREFSteven_S_Skiena2009" class="citation book cs1">Steven S Skiena (2009). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA77">The Algorithm Design Manual</a>. Springer Science & Business Media. p. 77. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-84800-070-4</bdi>.</cite>

</li>

<li id="cite_note-Knuth1997-3">^ <a href="#cite_ref-Knuth1997_3-0">a</a> <a href="#cite_ref-Knuth1997_3-1">b</a> <cite id="CITEREFKnuth1997" class="citation book cs1">Knuth (1997). The Art Of Computer Programming, Volume 1, 3/E. Pearson Education. p. 363. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-89683-4</bdi>.</cite>

</li>

<li id="cite_note-Flores1971-4"><a href="#cite_ref-Flores1971_4-0">^</a> <cite id="CITEREFIván_Flores1971" class="citation book cs1">Iván Flores (1971). Computer programming system/360. Prentice-Hall. p. 39.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFKenneth_Rosen2011" class="citation book cs1">Kenneth Rosen (2011). Discrete Mathematics and Its Applications, 7th edition. McGraw-Hill Science. p. 749. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-07-338309-5</bdi>.</cite>

</li>

<li id="cite_note-Mazur2010-6"><a href="#cite_ref-Mazur2010_6-0">^</a> <cite id="CITEREFDavid_R._Mazur2010" class="citation book cs1">David R. Mazur (2010). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=yI4Jx5Obr08C&pg=PA246">Combinatorics: A Guided Tour</a>. Mathematical Association of America. p. 246. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-88385-762-5</bdi>.</cite>

</li>

<li id="cite_note-oem-7">^ <a href="#cite_ref-oem_7-0">a</a> <a href="#cite_ref-oem_7-1">b</a> <cite class="citation cs2"><a rel="nofollow" class="external text" href="https://www.encyclopediaofmath.org/index.php?title=Binary_tree">"Binary tree"</a>, <a href="Encyclopedia_of_Mathematics" title="Encyclopedia of Mathematics">Encyclopedia of Mathematics</a>, <a href="European_Mathematical_Society" title="European Mathematical Society">EMS Press</a>, 2001 [1994]</cite> also in print as <cite id="CITEREFMichiel_Hazewinkel1997" class="citation book cs1">Michiel Hazewinkel (1997). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=3ndQH4mTzWQC&pg=PA124">Encyclopaedia of Mathematics. Supplement I</a>. Springer Science & Business Media. p. 124. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-7923-4709-5</bdi>.</cite>

</li>

<li id="cite_note-Foulds1992-8"><a href="#cite_ref-Foulds1992_8-0">^</a> <cite id="CITEREFL.R._Foulds1992" class="citation book cs1">L.R. Foulds (1992). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=IK7kreGl3vkC&pg=PA32">Graph Theory Applications</a>. Springer Science & Business Media. p. 32. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-97599-3</bdi>.</cite>

</li>

<li id="cite_note-Makinson2009b-9"><a href="#cite_ref-Makinson2009b_9-0">^</a> <cite id="CITEREFDavid_Makinson2009" class="citation book cs1">David Makinson (2009). Sets, Logic and Maths for Computing. Springer Science & Business Media. p. 199. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-84628-845-6</bdi>.</cite>

</li>

<li id="cite_note-Gross2007-10"><a href="#cite_ref-Gross2007_10-0">^</a> <cite id="CITEREFJonathan_L._Gross2007" class="citation book cs1">Jonathan L. Gross (2007). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=hamtabmh0ZoC&pg=PA248">Combinatorial Methods with Computer Applications</a>. CRC Press. p. 248. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-58488-743-0</bdi>.</cite>

</li>

<li id="cite_note-Long2018-11">^ <a href="#cite_ref-Long2018_11-0">a</a> <a href="#cite_ref-Long2018_11-1">b</a> <cite id="CITEREFLong2018" class="citation cs2">Long, Chengjiang (October 26, 2018), <a rel="nofollow" class="external text" href="https://www.chengjianglong.com/slides/DS_Lecture_22.pdf">Lecture 22: Recursive Definitions and Structural Induction</a> (PDF)</cite>

</li>

<li id="cite_note-Rosen2011-12">^ <a href="#cite_ref-Rosen2011_12-0">a</a> <a href="#cite_ref-Rosen2011_12-1">b</a> <cite id="CITEREFKenneth_Rosen2011" class="citation book cs1">Kenneth Rosen (2011). Discrete Mathematics and Its Applications 7th edition. McGraw-Hill Science. pp. 352–353. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-07-338309-5</bdi>.</cite>

</li>

<li id="cite_note-HuShing2002-13"><a href="#cite_ref-HuShing2002_13-0">^</a> <cite id="CITEREFTe_Chiang_HuMan-tak_Shing2002" class="citation book cs1">Te Chiang Hu; Man-tak Shing (2002). Combinatorial Algorithms. Courier Dover Publications. p. 162. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-486-41962-6</bdi>.</cite>

</li>

<li id="cite_note-HsuLin2008-14"><a href="#cite_ref-HsuLin2008_14-0">^</a> <cite id="CITEREFLih-Hsing_HsuCheng-Kuan_Lin2008" class="citation book cs1">Lih-Hsing Hsu; Cheng-Kuan Lin (2008). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=vbxdqhDKOSYC&pg=PA66">Graph Theory and Interconnection Networks</a>. CRC Press. p. 66. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4200-4482-9</bdi>.</cite>

</li>

<li id="cite_note-FlumGrohe2006-15"><a href="#cite_ref-FlumGrohe2006_15-0">^</a> <cite id="CITEREFJ._FlumM._Grohe2006" class="citation book cs1">J. Flum; <a href="Martin_Grohe" title="Martin Grohe">M. Grohe</a> (2006). Parameterized Complexity Theory. Springer. p. 245. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-29953-0</bdi>.</cite>

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <cite id="Goodrich" class="citation book cs1">Tamassia, Michael T. Goodrich, Roberto (2011). Algorithm design : foundations, analysis, and Internet examples (2 ed.). New Delhi: Wiley-India. p. 76. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-81-265-0986-7</bdi>.</cite><code class="cs1-code">{{cite book}}</code>: CS1 maint: multiple names: authors list (link)

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://xlinux.nist.gov/dads/HTML/fullBinaryTree.html">"full binary tree"</a>. <a href="NIST" class="mw-redirect" title="NIST">NIST</a>.</cite>

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> Richard Stanley, Enumerative Combinatorics, volume 2, p.36

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://xlinux.nist.gov/dads/HTML/perfectBinaryTree.html">"perfect binary tree"</a>. <a href="NIST" class="mw-redirect" title="NIST">NIST</a>.</cite>

</li>

<li id="cite_note-complete_binary_tree-20">^ <a href="#cite_ref-complete_binary_tree_20-0">a</a> <a href="#cite_ref-complete_binary_tree_20-1">b</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://xlinux.nist.gov/dads/HTML/completeBinaryTree.html">"complete binary tree"</a>. NIST.</cite>

</li>

<li id="cite_note-almost_complete_binary_tree-21"><a href="#cite_ref-almost_complete_binary_tree_21-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20160304081430/http://faculty.cs.niu.edu/~mcmahon/CS241/Notes/bintree.html">"almost complete binary tree"</a>. Archived from <a rel="nofollow" class="external text" href="http://faculty.cs.niu.edu/~mcmahon/CS241/Notes/bintree.html">the original</a> on 2016-03-04. Retrieved 2015-12-11.</cite>

</li>

<li id="cite_note-nearly_complete_binary_tree-22"><a href="#cite_ref-nearly_complete_binary_tree_22-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/nearly_complete.pdf">"nearly complete binary tree"</a> (PDF). <a rel="nofollow" class="external text" href="https://ghostarchive.org/archive/20221009/http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/nearly_complete.pdf">Archived</a> (PDF) from the original on 2022-10-09.</cite>

</li>

<li id="cite_note-23"><a href="#cite_ref-23">^</a> Aaron M. Tenenbaum, et al. Data Structures Using C, Prentice Hall, 1990 <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-13-199746-7</bdi>

</li>

<li id="cite_note-24"><a href="#cite_ref-24">^</a> Paul E. Black (ed.), entry for data structure in <a href="Dictionary_of_Algorithms_and_Data_Structures" class="mw-redirect" title="Dictionary of Algorithms and Data Structures">Dictionary of Algorithms and Data Structures</a>. U.S. <a href="National_Institute_of_Standards_and_Technology" title="National Institute of Standards and Technology">National Institute of Standards and Technology</a>. 15 December 2004. <a rel="nofollow" class="external text" href="https://xlinux.nist.gov/dads/HTML/balancedtree.html">Online version</a> Accessed 2010-12-19.

</li>

<li id="cite_note-25"><a href="#cite_ref-25">^</a> <cite id="CITEREFParmar2020" class="citation web cs1">Parmar, Anand K. (2020-01-22). <a rel="nofollow" class="external text" href="https://towardsdatascience.com/5-types-of-binary-tree-with-cool-illustrations-9b335c430254">"Different Types of Binary Tree with colourful illustrations"</a>. Medium. Retrieved 2020-01-24.</cite>

</li>

<li id="cite_note-26"><a href="#cite_ref-26">^</a> <cite id="CITEREFMehtaSartaj_Sahni2004" class="citation book cs1">Mehta, Dinesh; <a href="Sartaj_Sahni" title="Sartaj Sahni">Sartaj Sahni</a> (2004). Handbook of Data Structures and Applications. <a href="Chapman_and_Hall" class="mw-redirect" title="Chapman and Hall">Chapman and Hall</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1-58488-435-5</bdi>.</cite>

</li>

<li id="cite_note-Samanta2004-27"><a href="#cite_ref-Samanta2004_27-0">^</a> <cite id="CITEREFD._Samanta2004" class="citation book cs1">D. Samanta (2004). Classic Data Structures. PHI Learning Pvt. Ltd. pp. 264–265. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-81-203-1874-8</bdi>.</cite>

</li>

<li id="cite_note-Scott2009-28"><a href="#cite_ref-Scott2009_28-0">^</a> <cite id="CITEREFMichael_L._Scott2009" class="citation book cs1">Michael L. Scott (2009). Programming Language Pragmatics (3rd ed.). Morgan Kaufmann. p. 347. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-08-092299-7</bdi>.</cite>

</li>

<li id="cite_note-29"><a href="#cite_ref-29">^</a> <cite class="citation book cs1">Introduction to algorithms. Cormen, Thomas H., Cormen, Thomas H. (2nd ed.). Cambridge, Mass.: MIT Press. 2001. p. 128. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-262-03293-7</bdi>. <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/46792720">46792720</a>.</cite><code class="cs1-code">{{cite book}}</code>: CS1 maint: others (link)

</li>

<li id="cite_note-30"><a href="#cite_ref-30">^</a> <cite id="CITEREFLaakso" class="citation web cs1">Laakso, Mikko. <a rel="nofollow" class="external text" href="http://www.cse.hut.fi/en/research/SVG/TRAKLA2/tutorials/heap_tutorial/taulukkona.html">"Priority Queue and Binary Heap"</a>. University of Aalto. Retrieved 2023-10-11.</cite>

</li>

<li id="cite_note-31"><a href="#cite_ref-31">^</a> <cite id="CITEREFDemaine" class="citation web cs1">Demaine, Erik. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20051124175104/http://theory.csail.mit.edu/classes/6.897/spring03/scribe_notes/L12/lecture12.pdf">"6.897: Advanced Data Structures Spring 2003 Lecture 12"</a> (PDF). MIT CSAIL. Archived from <a rel="nofollow" class="external text" href="http://theory.csail.mit.edu/classes/6.897/spring03/scribe_notes/L12/lecture12.pdf">the original</a> (PDF) on 24 November 2005. Retrieved 14 April 2022.</cite>

</li>

<li id="cite_note-rice-32">^ <a href="#cite_ref-rice_32-0">a</a> <a href="#cite_ref-rice_32-1">b</a> <cite id="CITEREFDung_X._Nguyen2003" class="citation web cs1">Dung X. Nguyen (2003). <a rel="nofollow" class="external text" href="http://www.clear.rice.edu/comp212/03-spring/lectures/22/">"Binary Tree Structure"</a>. rice.edu. Retrieved December 28, 2010.</cite>

</li>

<li id="cite_note-33"><a href="#cite_ref-33">^</a> <cite id="CITEREFWittman2015" class="citation web cs1">Wittman, Todd (2015-02-13). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20150213195803/http://www.math.ucla.edu/~wittman/10b.1.10w/Lectures/Lec18.pdf">"Lecture 18: Tree Traversals"</a> (PDF). Archived from <a rel="nofollow" class="external text" href="http://www.math.ucla.edu/~wittman/10b.1.10w/Lectures/Lec18.pdf">the original</a> (PDF) on 2015-02-13. Retrieved 2023-04-29.</cite>

</li>

</ol></div>

<div class="mw-heading mw-heading3"><h3 id="Bibliography">Bibliography</h3></div>

<ul><li><a href="Donald_Knuth" title="Donald Knuth">Donald Knuth</a>. <a href="The_Art_of_Computer_Programming" title="The Art of Computer Programming">The Art of Computer Programming</a> vol 1. Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-89683-4</bdi>. Section 2.3, especially subsections 2.3.1–2.3.2 (pp. 318–348).</li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .infobox .side-box{font-size:100%}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1237033735">

/* start https://en.wikipedia.org/ */

@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="side-box side-box-right sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">

/* start https://en.wikipedia.org/ */

.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}

/* end https://en.wikipedia.org/ */

</style>

<div class="side-box-text plainlist">Wikimedia Commons has media related to <a href="https://commons.wikimedia.org/wiki/Category:Binary_trees" class="extiw external" title="commons:Category:Binary trees">Binary trees</a>.</div></div>

</div>

<ul><li><a rel="nofollow" class="external text" href="http://www.findstat.org/BinaryTrees">binary trees</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20200923083018/http://www.findstat.org/BinaryTrees">Archived</a> 2020-09-23 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a> entry in the <a rel="nofollow" class="external text" href="http://www.findstat.org/">FindStat</a> database</li>

<li><a rel="nofollow" class="external text" href="http://www.brpreiss.com/books/opus4/html/page355.html">Binary Tree Proof by Induction</a></li>

<li><a rel="nofollow" class="external text" href="http://piergiu.wordpress.com/2010/02/21/balanced-binary-search-tree-on-array/">Balanced binary search tree on array How to create bottom-up an Ahnentafel list, or a balanced binary search tree on array</a></li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20190407044321/http://www.cpphub.com/search/label/Binary%20trees">Binary trees and Implementation of the same with working code examples</a></li>

<li><a rel="nofollow" class="external text" href="https://lufemas.github.io/binary-tree-jr/">Binary Tree JavaScript Implementation with source code</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Tree_data_structures246" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Tree_data_structures246" style="font-size:114%;margin:0 4em"><a href="Tree_(abstract_data_type)" title="Tree (abstract data type)">Tree data structures</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Search_tree" title="Search tree">Search trees</a> (<a href="Set_(abstract_data_type)" title="Set (abstract data type)">dynamic sets</a>, <a href="Associative_array" title="Associative array">associative arrays</a>)</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="K-D-B-tree" title="K-D-B-tree">K-Dimensional</a></li></ul></li>

<li><a href="Binary_search_tree" title="Binary search tree">Binary search</a>

<ul><li><a href="Optimal_binary_search_tree" title="Optimal binary search tree">Optimal</a></li>

<li><a href="Self-balancing_binary_search_tree" title="Self-balancing binary search tree">Self-balancing</a></li></ul></li>

<li><a href="Dancing_tree" title="Dancing tree">Dancing</a></li>

<li><a href="HTree" title="HTree">HTree</a></li>

<li><a href="Interval_tree" title="Interval tree">Interval</a></li>

<li><a href="Order_statistic_tree" title="Order statistic tree">Order statistic</a></li>

<li><a href="Palindrome_tree" title="Palindrome tree">Palindrome</a></li>

<li>(<a href="Left-leaning_red%E2%80%93black_tree" title="Left-leaning red–black tree">Left-leaning</a>) <a href="Red%E2%80%93black_tree" title="Red–black tree">Red–black</a></li>

<li><a href="Scapegoat_tree" title="Scapegoat tree">Scapegoat</a></li>

<li><a href="Splay_tree" title="Splay tree">Splay</a></li>

<li><a href="Treap" title="Treap">Treap</a></li>

<li><a href="Weight-balanced_tree" title="Weight-balanced tree">Weight-balanced</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Heap_(data_structure)" title="Heap (data structure)">Heaps</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Binary_heap" title="Binary heap">Binary</a></li>

<li><a href="Binomial_heap" title="Binomial heap">Binomial</a></li>

<li><a href="Brodal_queue" title="Brodal queue">Brodal</a></li>

<li><a href="Fibonacci_heap" title="Fibonacci heap">Fibonacci</a></li>

<li><a href="Leftist_tree" title="Leftist tree">Leftist</a></li>

<li><a href="Pairing_heap" title="Pairing heap">Pairing</a></li>

<li><a href="Skew_binomial_heap" title="Skew binomial heap">Skew binomial</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Trie" title="Trie">Tries</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Ctrie" title="Ctrie">Ctrie</a></li>

<li><a href="C-trie" title="C-trie">C-trie</a> (compressed ADT)</li>

<li><a href="Radix_tree" title="Radix tree">Radix</a></li>

<li><a href="Suffix_tree" title="Suffix tree">Suffix</a></li>

<li><a href="Ternary_search_tree" title="Ternary search tree">Ternary search</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Spatial_index" class="mw-redirect" title="Spatial index">Spatial</a> data partitioning trees</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Cartesian_tree" title="Cartesian tree">Cartesian</a></li>

<li><a href="Hilbert_R-tree" title="Hilbert R-tree">Hilbert R</a></li>

<li><a href="K-d_tree" title="K-d tree">k-d</a> (<a href="Implicit_k-d_tree" title="Implicit k-d tree">implicit k-d</a>)</li>

<li><a href="Metric_tree" title="Metric tree">Metric</a></li>

<li><a href="Octree" title="Octree">Octree</a></li>

<li><a href="Priority_R-tree" title="Priority R-tree">Priority R</a></li>

<li><a href="Segment_tree" title="Segment tree">Segment</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other trees</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Cover_tree" title="Cover tree">Cover</a></li>

<li><a href="Exponential_tree" title="Exponential tree">Exponential</a></li>

<li><a href="Fenwick_tree" title="Fenwick tree">Fenwick</a></li>

<li><a href="Finger_tree" title="Finger tree">Finger</a></li>

<li><a href="Fractal_tree_index" title="Fractal tree index">Fractal index</a></li>

<li><a href="Fusion_tree" title="Fusion tree">Fusion</a></li>

<li><a href="Hash_calendar" title="Hash calendar">Hash calendar</a></li>

<li><a href="IDistance" title="IDistance">iDistance</a></li>

<li><a href="Left-child_right-sibling_binary_tree" title="Left-child right-sibling binary tree">Left-child right-sibling</a></li>

<li><a href="Log-structured_merge-tree" title="Log-structured merge-tree">Log-structured merge</a></li>

<li><a href="Merkle_tree" title="Merkle tree">Merkle</a></li>

<li><a href="Range_tree" title="Range tree">Range</a></li>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox authority-control" aria-labelledby="Authority_control_databases_frameless&#124;text-top&#124;10px&#124;alt=Edit_this_at_Wikidata&#124;link=https&#58;//www.wikidata.org/wiki/Q380172#identifiers&#124;class=noprint&#124;Edit_this_at_Wikidata529" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Authority_control_databases_frameless&#124;text-top&#124;10px&#124;alt=Edit_this_at_Wikidata&#124;link=https&#58;//www.wikidata.org/wiki/Q380172#identifiers&#124;class=noprint&#124;Edit_this_at_Wikidata529" style="font-size:114%;margin:0 4em">Authority control databases </div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">National</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4145532-0">Germany</a></li></ul></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><a rel="nofollow" class="external text" href="https://lux.collections.yale.edu/view/concept/d3c8ea88-4745-46a1-98e1-c792754d5ea0">Yale LUX</a></li></ul></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-24" href="https://en.wikipedia.org/wiki/?title=Binary_tree&oldid=1302319250">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>